import java.util.Arrays;

public class quickSort {
    public static void Qsort(int[] nums){
        if(nums == null || nums.length == 0){
            return;
        }
        sort(nums,0,nums.length-1);
    }
    private static  void sort(int[] nums,int lo,int hi){
        if(lo >= hi) return;
        int j = partition(nums,lo,hi);
        sort(nums,lo,j-1);
        sort(nums,j+1,hi);
    }

    private static int partition(int[] nums,int lo,int hi){
//        int pivot = hi;
        int pivot = nums[hi];
//        int less = 0 , great = 0;
        int less = lo,great=lo;
//        for (;great < nums.length-2;great++){
//            if (nums[great] > nums[pivot]){
//                swap(nums,less,great);
//                less++;
//            }
//        }
        for (;great <= hi-1;great++){
            if(pivot > nums[great]){
                swap(nums,great,less);
                less++;
            }
        }
//        swap(nums,less,pivot);
        swap(nums,less,hi);
        return less;
    }

    private static void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    public static void main(String[] str){
        int[] nums = {22,31,2,1,5,10};
        Qsort(nums);
        System.out.println(Arrays.toString(nums));
    }
}
